package LeetCodeHot100TopInterview;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Q078_SubSet {
    //子集 subset
    //输入：nums = [1,2,3]
    //输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
    // ==> 广度优先  nonono ==> [子序列问题] || 全排列问题也要熟！！
    List<List<Integer>> ans = null;
    public List<List<Integer>> subsets(int[] nums) {
        if (nums == null || nums.length == 0){
            return new ArrayList<>();
        }
        ans = new LinkedList<>();
        process(nums, 0, new LinkedList<>());
        return ans;
    }

    public void process(int[] nums, int index, LinkedList<Integer> path ){

        if (index == nums.length){
            LinkedList<Integer> tmp = new LinkedList<>(path);
            ans.add(tmp);
            return;
        }
        //no
        process(nums, index + 1, path);
        //yes
        path.add(nums[index]);
        process(nums, index + 1, path);
        //cover
        path.removeLast();
    }


}
